package com.peng.leetcode.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * ZigzagLevelOrder
 * 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 *
 * @author: lupeng6
 * @create: 2020/12/2 15:31
 */
public class ZigzagLevelOrder {


    static class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            if (root == null) {
                return res;
            }
            dfs(root, 0, res);
            return res;
        }

        private void dfs(TreeNode node, int level, List<List<Integer>> res) {
            if (level >= res.size()) {
                res.add(new LinkedList<>());
            }
            if (level % 2 == 0) {
                // 左插入
                res.get(level).add(node.val);
            } else {
                // 右插入
                res.get(level).add(0, node.val);
            }
            if (node.left != null) {
                dfs(node.left, level + 1, res);
            }
            if (node.right != null) {
                dfs(node.right, level + 1, res);
            }
        }
    }

}
